
from collections import defaultdict
from build_undirected_graph import *


class UnDirectedGraphNode:
    def __init__(self, x):
        self.label = x
        self.neighbors = []

    def __str__(self):
        return str(self.label)

# 无向图的连通分量使用BFS/DFS/union find即可计算(这里不予展示)

# =================== cut point =====================
def cut_points_tarjan(graph):
    # 连通图的cut_point 才有意义(割点把连通图分成多个不连通图)
    # tarjan算法, (一次dfs即可)

    non_visited = set(graph)
    ret_cut_points = []

    node = non_visited.pop()
    dfn = {}    # label : dfn
    low = {}    # label : low link value
    child_cnt  = defaultdict(int) # label: cnt
    stack = []
    order = 0

    _dfs_tarjan_cut_point(node, UnDirectedGraphNode('dummy'), dfn, low, child_cnt, stack, order, non_visited, ret_cut_points)
    return ret_cut_points

def _dfs_tarjan_cut_point(node, parent, dfn, low, child_cnt, stack, order, non_visited, ret_cut_points):
    stack.append(node)
    label = node.label
    dfn[label] = low[label] = order
    # print('label, parent, dfn, low %s %s %s %s' % ( label, parent.label, dfn[label], low[label] ))
    # print('neis %s' % node.neighbors)

    for nei in node.neighbors:
        # 区分根节点和非叶子节点
        if nei is parent:
            continue

        nei_label = nei.label
        # print('     ----> nei_label %s' % nei_label)

        if nei not in non_visited:
            if nei in stack:
                low[label] = min(low[label], low[nei_label])
        else:
            child_cnt[node.label] += 1          # 这个变量主要是给root节点使用
            non_visited.remove(nei)
            nei_low = _dfs_tarjan_cut_point(nei, node, dfn, low, child_cnt, stack, order + 1, non_visited, ret_cut_points)
            # NOTE: WARNING: 这里是nei_low >= dfn[label], 而不是low[label]
            if dfn[label] != 0 and nei_low >= dfn[label]:
                # 存在子节点最大只能到达当前节点: 那么当前节点一定是割点
                if node not in ret_cut_points:
                    ret_cut_points.append(node)

            # 否则先更新后则: low[nei_label] == low[label], nei_low >= low[label] 会match(但并不应该match)
            low[label] = min(low[label], nei_low)

    if dfn[label] == 0 and child_cnt[label] > 1:
        # print('===================  root is cut point')
        ret_cut_points.append(node)

    return low[label]


# =================== cut edge =====================
def cut_edges_tarjan(graph):
    # 连通图的cut_edges 才有意义(割边把连通图分成多个不连通图)
    non_visited = set(graph)
    ret_cut_edges = []

    node = non_visited.pop()
    dfn = {}    # label : dfn
    low = {}    # label : low link value
    stack = []
    order = 0

    # 这里不用循环遍历所有non_visited(假设图是连通的, 一次就可以遍历完)
    _dfs_tarjan_cut_edge(node, UnDirectedGraphNode('dummy'), dfn, low, stack, order, non_visited, ret_cut_edges)
    return ret_cut_edges

def _dfs_tarjan_cut_edge(node, parent, dfn, low, stack, order, non_visited, ret_cut_edges):
    stack.append(node)
    label = node.label
    dfn[label] = low[label] = order

    for nei in node.neighbors:
        if nei is parent:
            continue

        nei_label = nei.label

        if nei not in non_visited:
            if nei in stack:
                low[label] = min(low[label], low[nei_label])

        if nei in non_visited:
            non_visited.remove(nei)
            nei_low = _dfs_tarjan_cut_edge(nei, node, dfn, low, stack, order + 1, non_visited, ret_cut_edges)
            if nei_low > dfn[label]:
                # NOTE:注意是>, 而非">="(表示子节点通过父边外无法到达当前node, 那么之间一定存在割边)
                if (node, nei) not in ret_cut_edges:
                    ret_cut_edges.append((node, nei))
                    pass

            low[label] = min(low[label], nei_low)

    return low[label]

# =================== check is biconnected =====================
def is_biconnected_graph(graph):
    # 连通图的cut_point 才有意义(割点把连通图分成多个不连通图)
    # tarjan算法, (一次dfs即可)

    non_visited = set(graph)
    ret_cut_points = []

    node = non_visited.pop()
    dfn = {}    # label : dfn
    low = {}    # label : low link value
    child_cnt  = defaultdict(int) # label: cnt
    stack = []
    order = 0

    _, is_biconnected = _dfs_tarjan_biconnected(node, UnDirectedGraphNode('dummy'), dfn, low, child_cnt, stack, order, non_visited)
    if not is_biconnected:
        return False
    else:
        # print('here')
        return not non_visited

def _dfs_tarjan_biconnected(node, parent, dfn, low, child_cnt, stack, order, non_visited):
    stack.append(node)
    label = node.label
    dfn[label] = low[label] = order
    # print('label, parent, dfn, low %s %s %s %s' % ( label, parent.label, dfn[label], low[label] ))
    # print('neis %s' % node.neighbors)

    for nei in node.neighbors:
        # 区分根节点和非叶子节点
        if nei is parent:
            continue

        nei_label = nei.label
        # print('     ----> nei_label %s' % nei_label)

        if nei not in non_visited:
            if nei in stack:
                low[label] = min(low[label], low[nei_label])
        else:
            child_cnt[node.label] += 1          # 这个变量主要是给root节点使用
            non_visited.remove(nei)
            nei_low, is_biconnected = _dfs_tarjan_biconnected(nei, node, dfn, low, child_cnt, stack, order + 1, non_visited)
            # NOTE: WARNING: 这里是nei_low >= dfn[label], 而不是low[label]
            if not is_biconnected:
                return -1, False

            if dfn[label] != 0 and nei_low >= dfn[label]:
                # 存在子节点最大只能到达当前节点: 那么当前节点一定是割点(一定不是连通图)
                return -1, False

            # 否则先更新后则: low[nei_label] == low[label], nei_low >= low[label] 会match(但并不应该match)
            low[label] = min(low[label], nei_low)

    if dfn[label] == 0 and child_cnt[label] > 1:
        return low[label], False

    return low[label], True

# =================== test =====================
def test_cut_point():
    graph = build_classic_undirected_graph()
    ret = cut_points_tarjan(graph)
    print("count of cut points %s" % len(ret))
    for node in ret:
        print(node)

# =================== test =====================
def test_cut_edge():
    graph = build_classic_undirected_graph()
    ret = cut_edges_tarjan(graph)
    print("count of cut edges %s" % len(ret))
    for src, dst in ret:
        print('cut edge between %s ------> %s' % (src, dst))

def test_is_biconnected_graph():
    graph = build_classic_undirected_graph()
    ret = is_biconnected_graph(graph)
    print("is biconnected %s" % ret)

def main():
    print("start main")
    # test_cut_point()
    # test_cut_edge()
    test_is_biconnected_graph()

if __name__ == "__main__":
    main()

